package com.example.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class ReversePolishNotation {

    public static void main(String[] args) {
        String expression = "1+((2+3)*4)-5";
        ReversePolishNotation reversePolishNotation = new ReversePolishNotation();
        List<String> data = reversePolishNotation.addData(expression);
        // 获取逆波兰表达式（后缀表达式）
        List<String> list = reversePolishNotation.reversePolishExpressionConversion(data);
        // 根据逆波兰表达式进行计算
        int cal = reversePolishNotation.cal(list);
        System.out.println(list);
        System.out.println("计算结果："+cal);
    }

    // 根据传入的List集合生成对应的后缀表达式（逆波兰表达式）
    public List<String> reversePolishExpressionConversion(List<String> data) {
        Stack<String> s1 = new Stack<>();
        List<String> s2 = new ArrayList<>();
        for (String item : data) {
            if (item.matches("\\d+")) {
                s2.add(item);
            } else {
                if (s1.empty() || "(".equals(item)) {
                    s1.push(item);
                } else if (s1.empty() || ")".equals(item)) {
                    while (!s1.peek().equals("(")) {
                        s2.add(s1.pop());
                    }
                    // 弹出左括号
                    s1.pop();
                } else {
                    // 如果栈顶的符号，优先级比item高，将栈顶符号弹出加入到s2
                    while (s1.size() != 0 && getOperatorPriority(s1.peek()) > getOperatorPriority(item)) {
                        s2.add(s1.pop());
                    }
                    // 否则将item压入到栈顶
                    s1.push(item);
                }
            }
        }
        while (!s1.empty()) {
            s2.add(s1.pop());
        }
        return s2;
    }

    public List<String> addData(String expression) {
        List<String> dataList = new ArrayList<>();
        String[] chars = expression.split("");
        int index = 0;
        do {
            if (index >= expression.length()) {
                break;
            }
            String value = chars[index];
            if (isOperator(value)) {
                dataList.add(value);
                index++;
            } else {
                while (true) {
                    // 当前索引不超过数组最大值并且下一位仍然是数字
                    if (index < chars.length - 1 && !isOperator(chars[index + 1])) {
                        value += chars[index + 1];
                        index++;
                    } else {
                        break;
                    }
                }
                dataList.add(value);
                index++;
            }
        } while (true);
        return dataList;
    }



    public boolean isOperator(String value) {
        return value.charAt(0) < 48 || value.charAt(0) > 57;
    }

    public int cal(List<String> data) {
        Stack<String> stack = new Stack();
        for (String item : data) {
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                int res = 0;
                int num2 = Integer.valueOf(stack.pop());
                int num1 = Integer.valueOf(stack.pop());
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                }
                stack.push("" + res);
            }
        }
        return Integer.valueOf(stack.pop());
    }

    public int getOperatorPriority(String operator) {
        int priority = 0;
        switch (operator) {
            case "+":
                priority = 1;
            case "-":
                priority = 1;
            case "*":
                priority = 2;
            case "/":
                priority = 2;
            default:
                System.out.println("操作符输入错误");
        }
        return priority;
    }
}
